package com.wtgroup.demo.mianshi.算法.二分法;

/**
 * 有序数组里, 查找最接近(<,<=,>,>=)目标值的下标
 *
 * @author nisus
 * @since 2025/3/6 13:06
 */
public class SearchNearTarget {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3, 4, 4, 5};
        System.out.println(greaterEqual(arr, 3));
        System.out.println(greaterEqual(arr, 1));
        System.out.println(greaterEqual(arr, 5));
        System.out.println(greaterEqual(arr, 100));
        System.out.println(greaterEqual(arr, 2));
    }

    // 找哪一侧区域的, 就优先移动哪一侧指针, 最后返回另一侧指针就是答案
    // 如 < target, 即找左侧的, 优先考虑移动左指针
    static int lessThan(int[] arr, int target) {
        int L = 0;
        int R = arr.length - 1;
        while (L <= R) {
            int mid = L + (R - L) / 2;
            if (arr[mid] < target) {
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return R > arr.length - 1 ? -1 : R;
    }

    static int greaterThan(int[] arr, int target) {
        int L = 0;
        int R = arr.length - 1;
        while (L <= R) {
            int mid = L + (R - L) / 2;
            if (arr[mid] > target) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return L > arr.length - 1 ? -1 : L;
    }

    static int greaterEqual(int[] arr, int target) {
        int L = 0;
        int R = arr.length - 1;
        while (L <= R) {
            int mid = L + (R - L) / 2;
            if (arr[mid] >= target) { // 加上 "="
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return L > arr.length - 1 ? -1 : L;
    }
}
